package LeetCode;

import java.util.Arrays;

public class No34 {
    public static void main(String[] args) {
        int[] nums = {5,7,7,8,8,10};
        System.out.println(Arrays.toString(searchRange(nums, 8)));
    }

    public static int[] searchRange(int[]nums,int target){
        int start =getvalue(nums,target,true);
        int end =getvalue(nums,target,false)-1;
        System.out.println("start = " + start);
        System.out.println("end = " + end);
        if(start<=end&&start>=0&&end<nums.length&&nums[start]==target&&nums[end]==target){
            return new int[]{start,end};
        }
        return new int[]{-1,-1};
    }

        public static int getvalue(int[] nums,int target,boolean lower){
            int left = 0, right = nums.length-1,ans = nums.length;
            while(left<=right){
                int mid = (left+right)/2;
                if(nums[mid]>target||(lower&&nums[mid]>=target)){
                    right = mid-1;
                    ans=mid;
                }
                else left=mid+1;
            }
            if(lower) return left;
            else{
                return ans;
            }
        }

    public static int[] searchRange1(int[] nums, int target) {
        int start = 0, end = nums.length-1;
        while(start<=end){
            int i = (start+end)/2;
            if(nums[i]>target) end= i-1;
            if(nums[i]<target) start= i+1;
            if(nums[i]==target) {
                if(i>=0){
                    start=i-1;
                    while(start>=0&&nums[start]==target){
                        start--;
                    }
                }
                if(i<=nums.length-1){
                    end=i+1;
                    while(end<=nums.length-1&&nums[end]==target){
                        end++;
                    }
                }
                return new int[]{start+1,end-1};
            }
        }
        return new int[]{-1,-1};
    }
}
